/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/add-two-numbers-ii
   @Language: C++
   @Datetime: 19-03-24 16:40
   */

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
	ListNode *reverse(ListNode *head){
		ListNode *p=NULL, *t;
		for(; head; head=t){
			t=head->next;
			head->next=p;
			p=head;
		}
		return p;
	}
public:
	/**
	 * @param l1: The first list.
	 * @param l2: The second list.
	 * @return: the sum list of l1 and l2.
	 * Tip:
	 * reverse l1, l2, add and build new list with head insert
	 */
	ListNode * addLists2(ListNode * l1, ListNode * l2) {
		// write your code here
		if(l1==NULL || l2==NULL) return l1?l1:l2;
		l1=reverse(l1), l2=reverse(l2);
		ListNode *p=NULL;
		for(int carry=0; l1 || l2 || carry; carry/=10){
			if (l1) carry += l1->val, l1=l1->next;
			if (l2) carry += l2->val, l2=l2->next;
			p=new ListNode(carry%10,p);
		}
		return p;
	}
};
